#include<stdio.h>
#include<stdlib.h>
/**
*  Tutorial #10 (Merge and Quick Sort)
*  Program to Quick Sort
**/
int main5(){
    printf("Enter the Number Count\n");
    int n;
    scanf("%d",&n);
    printf("Enter %d numbers\n",n);
    int ar[n],i;
    for(i = 0;i < n;i++){
        scanf("%d",&ar[i]);
    }
    quickSort(ar,0,n-1);
    printf("The Sorted Numbers are");
    for(i = 0;i < n;i++){
        printf("%d ",ar[i]);
    }
}

void quickSort(int ar[],int i,int j){
    if(i >= j){
      return;
    }else{
      int l;
      seperateArray(ar,i,j,&l);
      quickSort(ar,i,l-1);
      quickSort(ar,l+1,j);
    }
}

void seperateArray(int ar[],int i,int j,int *l){
    int b1[100],b2[100],sep = ar[i];
    int start = i,end = j,index_b1 = 0,index_b2 = 0;
    b1[index_b1] = ar[i];
    i++;
    index_b1++;
    while(i <= j ){
        if(ar[i] <= sep){
            b1[index_b1] = ar[i];
            index_b1++;
        }else{
            b2[index_b2] = ar[i];
            index_b2++;
        }
        i++;
    }
    int b1_end = index_b1 -1,b2_end = index_b2 - 1;
    index_b1 = 0,index_b2 = 0;
    while(start <= end){
        if(index_b1 <= b1_end){
           ar[start] = b1[index_b1];
           index_b1++;
        }else{
            if(index_b2 == 0){
                *l = start - 1;
            }
            ar[start] = b2[index_b2];
            index_b2++;
        }
        start++;
    }
}
